Data Structures and Algorithms for Job Interviews by Alejandro Garcia

Author:Alejandro Garcia [Alejandro Garcia]
Language: eng
Format: epub, pdf
Publisher: leanpub.com
Published: 2020-08-15T00:00:00+00:00

Find if linked list contains any cycle

1 # Python program to check if the singly linked list contains cycle or not 2 3 4 # Node class 5 class Node: 6 7 # Constructor to initialise data and next 8 def __init__(self, data=None): 9 self.data = data 10 self.next = None 11 12 13 class SinglyLinkedList: 14 15 # Constructor to initialise head 16 def __init__(self): 17 self.head = None 18 19 # Function to find cycle in linked list 20 def find_cycle(self): 21 fast = self.head.next 22 slow = self.head 23 24 # Make fast run twice the speed of slow 25 # if fast coincide with slow 26 # then there is a loop or cycle 27 while fast is not None: 28 # return True if cycle 29 if fast is slow: 30 return True 31 fast = fast.next 32 if fast is not None: 33 fast = fast.next 34 slow = slow.next 35 36 # return False if no cycle 37 return False 38 39 # Function to Insert data at the beginning of the linked list 40 def insert_at_beg(self, data): 41 node = Node(data) 42 node.next = self.head 43 self.head = node 44 45 # Function to print the linked list 46 def print_data(self): 47 current = self.head 48 while current is not None: 49 print(current.data, '-> ', end='') 50 current = current.next 51 print('None') 52 53 if __name__ == '__main__': 54 linked_list = SinglyLinkedList() 55 linked_list.insert_at_beg(9) 56 linked_list.insert_at_beg(8) 57 linked_list.insert_at_beg(7) 58 linked_list.insert_at_beg(6) 59 linked_list.insert_at_beg(5) 60 linked_list.insert_at_beg(4) 61 linked_list.insert_at_beg(3) 62 linked_list.insert_at_beg(2) 63 linked_list.insert_at_beg(1) 64 65 temp = head = linked_list.head 66 67 # get pointer to the end of the list 68 while temp.next is not None: 69 temp = temp.next 70 71 # Make a loop in the list 72 temp.next = head.next.next.next 73 74 # call the find_cycle function 75 result = linked_list.find_cycle() 76 77 # print if cycle or not 78 print('Yes! there is a cycle') if result else print('No! there is no cycle')

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.